
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1663. -- [Usaco2006 Open] -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>1663: [Usaco2006 Open]</h2><span class=green>Time Limit: </span>5 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>64 MB<br><span class=green>Submit: </span>93&nbsp;&nbsp;<span class=green>Solved: </span>46<br>[<a href='submitpage.php?id=1663'>Submit</a>][<a href='problemstatus.php?id=1663'>Status</a>][<a href='bbs.php?id=1663'>Discuss</a>]</center><h2>Description</h2><div class=content>
Every year, Farmer John loves to attend the county fair. The fair 
has N booths (1 <= N <= 400), and each booth i is planning to give 
away a fabulous prize at a particular time P(i) (0 <= P(i) <= 
1,000,000,000) during the day. Farmer John has heard about this 
and would like to collect as many fabulous prizes as possible to 
share with the cows. He would like to show up at a maximum possible 
number of booths at the exact times the prizes are going to be 
awarded. 

Farmer John investigated and has determined the time T(i,j) (always 
in range 1..1,000,000) that it takes him to walk from booth i to 
booth j. The county fair's unusual layout means that perhaps FJ 
could travel from booth i to booth j by a faster route if he were 
to visit intermediate booths along the way. Being a poor map reader, 
Farmer John never considers taking such routes -- he will only walk 
from booth i to booth j in the event that he can actually collect 
a fabulous prize at booth j, and he never visits intermediate booths 
along the way. Furthermore, T(i,j) might not have the same value 
as T(j,i) owing to FJ's slow walking up hills. 

Farmer John starts at booth #1 at time 0. Help him collect as many 
fabulous prizes as possible. 


题目给出了N个收藏品，每个收藏品都会在某个时间在固定的地方掉下来 
比如说第i个东西会在Ti的时间在N号点掉下来。 
FJ一开始在1号点，每次他可以选择一个地点然后笔直（不经过其他点）走过去在那个地点等着， 
直到那个收藏品掉下来然后拿起来,如果这个东西FJ是不打算拾的话，那么他是不能走到这个点的. 
也就是你从某个出发点到某个目标点，你不能经由中转站的. 
我们需要帮助FJ找出他最多能够收集到多少的收藏品。</div><h2>Input</h2><div class=content>* Line 1: A single integer, N. 
* Lines 2..1+N: Line i+1 contains a single integer, P(i). 
* Lines 2+N..1+N+N^2: These N^2 lines each contain a single integer 
T(i,j) for each pair (i,j) of booths. The first N of these 
lines respectively contain T(1,1), T(1,2), ..., T(1,N). The 
next N lines contain T(2,1), T(2,2), ..., T(2,N), and so on. 
Each T(i,j) value is in the range 1...1,000,000 except for the 
diagonals T(1,1), T(2,2), ..., T(N,N), which have the value 
zero. 

</div><h2>Output</h2><div class=content>* Line 1: A single integer, containing the maximum number of prizes 
Farmer John can acquire. 

</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata><br />
4 //有四个收藏品可以去收集,下面四行给出这四个东西下落的时间<br />
13 //第一个东西，在第一个地点第13分钟掉下来<br />
9 //第二个东西，在第二个地点第9分钟掉下来<br />
19 //第三个东西，在第三个地点第19分钟掉下来<br />
3 //这是第四个东西.<br />
0 //这下面有4*4行，代表每个点到其它点的要花的时间，自己到自己的时间为0。<br />
10<br />
20<br />
3<br />
4<br />
0<br />
11<br />
2<br />
1<br />
15<br />
0<br />
12<br />
5<br />
5<br />
13<br />
0<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>3<br />
<br />
Farmer John first walks to booth #4 and arrives at time 3, just in<br />
time to receive the fabulous prize there. He them walks to booth<br />
#2 (always walking directly, never using intermediate booths!) and<br />
arrives at time 8, so after waiting 1 unit of time he receives the<br />
fabulous prize there. Finally, he walks back to booth #1, arrives<br />
at time 13, and collects his third fabulous prize.<br />
</span></div><h2>HINT</h2>
			<div class=content><p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=Silver'>Silver</a></p></div><center>[<a href='submitpage.php?id=1663'>Submit</a>][<a href='problemstatus.php?id=1663'>Status</a>][<a href='bbs.php?id=1663'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
